package paths.g4;

import java.util.*;

import paths.*;

public class Util {
  public static boolean[][] FindAllPossibleRoutes(
      ArrayList<City> cities_arraylist,
      ArrayList<Link> links_arraylist,
      String start_city_name) throws Exception {
    int num_city = cities_arraylist.size();
    boolean reachable[]=new boolean[num_city];
    for(int k=0;k<num_city;k++)
    {
    	reachable[k]=false;
    }
    int start_city_idx = getCityIdxByName(start_city_name, cities_arraylist);
    City start_city = cities_arraylist.get(start_city_idx);
    reachable[start_city_idx]=false;
    boolean links_to_east[][] = new boolean[num_city][num_city];
    boolean links_to_west[][] = new boolean[num_city][num_city];
    for (Link link: links_arraylist) {
      int src_idx = getCityIdxByName(link.src, cities_arraylist);
      int dest_idx = getCityIdxByName(link.dest, cities_arraylist);
      if (isValidLinkToEast(cities_arraylist.get(src_idx).x,
                            cities_arraylist.get(dest_idx).x,
                            start_city.x)) {
        links_to_east[src_idx][dest_idx] = true;
        links_to_west[dest_idx][src_idx] = true;
      }
      if (isValidLinkToEast(cities_arraylist.get(dest_idx).x,
                            cities_arraylist.get(src_idx).x,
                            start_city.x)) {
        links_to_east[dest_idx][src_idx] = true;
        links_to_west[src_idx][dest_idx] = true;
      }
    }

    boolean reachable_links_to_east[][] =
        removeUnusedLinks(links_to_east, start_city_idx);
    boolean reachable_links_to_west[][] =
        removeUnusedLinks(links_to_west, start_city_idx);
    boolean reachable_links[][] = new boolean[num_city][num_city];

    for (int i = 0; i < num_city; i++) {
      for (int j = 0; j < num_city; j++) {
        reachable_links[i][j] =
            reachable_links_to_east[i][j] && reachable_links_to_west[j][i];
      }
    }
    return reachable_links;
  }

  static boolean[][] removeUnusedLinks(boolean links[][], int start_city_idx) {
    int num_city = links.length;
    boolean visited_city[] = new boolean[num_city];
    boolean visited_links[][] = new boolean[num_city][num_city];
    LinkedList<Integer> queue = new LinkedList<Integer>();
    queue.offer(start_city_idx);
    visited_city[start_city_idx] = true;
    while (queue.peek() != null) {
      int src = queue.poll();
      for (int dest = 0; dest < num_city; dest++) {
        if (links[src][dest]) {
          visited_links[src][dest] = true;
          if (!visited_city[dest]) {
            queue.offer(dest);
            visited_city[dest] = true;
          }
        }
      }
    }
    return visited_links;
  }

  static boolean isValidLinkToEast(float lat1, float lat2, float lat_start_city) {
    lat1 = (lat1 - lat_start_city + 360) % 360;
    lat2 = (lat2 - lat_start_city + 360) % 360;
    return lat2 > lat1 || lat2 < 0.0000001;
  }

  static public int getCityIdxByName(String name, ArrayList<City> cities)
      throws Exception {
    for (int i = 0; i < cities.size(); i++) {
      City city = cities.get(i);
      if(name.equalsIgnoreCase(city.name))
        return i;
    }
    System.out.println("can't find city name " + name);
    throw new Exception("can't find city name " + name);
  }

  static public Random rand = new Random();

  // find a route from the start city, go around the world and back to the
  // start city. The last stop is not included in the output.
  static public ArrayList<Integer> FindRandomRoute(
      boolean reachable_links[][], int start_city_idx) {
    int num_city = reachable_links.length;
    int current_city = start_city_idx;
    ArrayList<Integer> route = new ArrayList<Integer>();
    while (true) {
      route.add(current_city);
      while (true) {
        int next_city = (int) (rand.nextDouble() * num_city);
        // Try again if the route is too short.
        if (next_city == start_city_idx && route.size() < 2)
          continue;
        if (reachable_links[current_city][next_city]) {
          current_city = next_city;
          // If goes back to the starting city, end the trip.
          if (current_city == start_city_idx) {
            return route;
          }
          break;
        }
      }
    }
  }

  static public ArrayList<Integer> findLongestRoute(
      ArrayList<City> cities_arraylist,
      boolean reachable_links[][], int start_city_idx) {
    int num_city = cities_arraylist.size();
    Integer city_order[] = new Integer[num_city];
    Integer next_city[] = new Integer[num_city];
    Integer num_stops[] = new Integer[num_city];
    for (int i = 0; i < num_city; i++) {
      city_order[i] = i;
      next_city[i] = -1;
      num_stops[i] = -1;
    }

    Arrays.sort(city_order,
                new CityIdxLngComparator(cities_arraylist, start_city_idx));

    num_stops[start_city_idx] = 0;
    for (int i = num_city - 1; i >= 0; i--) {
      int current_city = city_order[i];
      int best_next_stop = -1;
      int best_num_stops = -1;
      for (int j = 0; j < num_city; j++) {
        if (reachable_links[current_city][j]) {
          if (num_stops[j] + 1 > best_num_stops) {
            best_num_stops = num_stops[j] + 1;
            best_next_stop = j;
          }
        }
        num_stops[current_city] = best_num_stops;
        next_city[current_city] = best_next_stop;
      }
    }

    ArrayList<Integer> route = new ArrayList<Integer>();
    route.add(start_city_idx);
    for (int i = next_city[start_city_idx]; i != start_city_idx; i = next_city[i]) {
      route.add(i);
    }
    return route;
  }

  // Remove routes like "start_city -> some_city -> start_city"
  static public void removeShortRoutes(boolean links[][], int start_city_idx) {
    int num_city = links.length;
    for (int i = 0; i < num_city; i++) {
      int in_degree = 0;
      int out_degree = 0;
      for (int j = 0; j < num_city; j++) {
        if (links[i][j]) out_degree++;
        if (links[j][i]) in_degree++;
      }
      if (in_degree <= 1 && out_degree <= 1 &&
          links[i][start_city_idx] && links[start_city_idx][i]) {
        System.out.println("remove city " + i);
        for (int j = 0; j < num_city; j++) {
          links[i][j] = false;
          links[j][i] = false;
        }
      }
      if (in_degree == 1 && links[start_city_idx][i] && links[i][start_city_idx])
        links[i][start_city_idx] = false;
      if (out_degree == 1 && links[start_city_idx][i] && links[i][start_city_idx])
        links[start_city_idx][i] = false;
    }
  }

  static public int[] getInDegree(boolean links[][]) {
    int num_city = links.length;
    int in_degree[] = new int[num_city];
    for (int i = 0; i < num_city; i++) {
      in_degree[i] = 0;
      for (int j = 0; j < num_city; j++) {
        if (links[j][i]) in_degree[i]++;
      }
    }
    return in_degree;
  }

  static public int[] getOutDegree(boolean links[][]) {
    int num_city = links.length;
    int out_degree[] = new int[num_city];
    for (int i = 0; i < num_city; i++) {
      out_degree[i] = 0;
      for (int j = 0; j < num_city; j++) {
        if (links[i][j]) out_degree[i]++;
      }
    }
    return out_degree;
  }

  static public boolean[][] runWarshall(boolean links[][], int start_city_idx) {
    int num_city = links.length;
    boolean connected[][] = new boolean[num_city][num_city];
    // Copy from links to connected
    for (int i = 0; i < num_city; i++) {
      for (int j = 0; j < num_city; j++) {
        connected[i][j] = links[i][j];
      }
    }

    // Warshall algorithm
    for (int k = 0; k < num_city; k++) {
      for (int i = 0; i < num_city; i++) {
        for (int j = 0; j < num_city; j++) {
          if (connected[i][k] && connected[k][j] && k != start_city_idx)
            connected[i][j] = true;
        }
      }
    }
    return connected;
  }

  static public boolean[][] getDominantLinks(boolean connected[][], int start_city_idx) {
    int num_city = connected.length;
    boolean dominant_links[][] = new boolean[num_city][num_city];
    // Copy from connected to dominant_links
    for (int i = 0; i < num_city; i++) {
      for (int j = 0; j < num_city; j++) {
        dominant_links[i][j] = connected[i][j];
      }
    }

    for (int i = 0; i < num_city; i++) {
      for (int j = 0; j < num_city; j++) {
        for (int k = 0; k < num_city; k++) {
          if (connected[i][k] && connected[k][j] && k != start_city_idx)
            dominant_links[i][j] = false;
        }
      }
    }
    return dominant_links;
  }
}

// Takes the city indices, compare their longitude.
class CityIdxLngComparator implements Comparator<Integer> {
  private ArrayList<City> cities;
  private int start_city_idx;
  private float lat_start_city;

  public CityIdxLngComparator(
      ArrayList<City> cities_arraylist, int start_city_idx) {
    cities = cities_arraylist;
    this.start_city_idx = start_city_idx;
    lat_start_city = cities.get(start_city_idx).x;
  }

  public int compare(Integer a, Integer b) {
    float lat1 = cities.get(a.intValue()).x;
    float lat2 = cities.get(b.intValue()).x;
    lat1 = (lat1 - lat_start_city + 360) % 360;
    lat2 = (lat2 - lat_start_city + 360) % 360;
    if (lat1 > lat2)
      return 1;
    else if (lat2 == lat1)
      return 0;
    else
      return -1;
  }
}

